package leetcode_题库;

import java.util.HashSet;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/24 15:08 星期三
 */
public class _83_删除排序链表中的重复元素 {
    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(6);
        ListNode n4 = new ListNode(3);
        ListNode n5 = new ListNode(4);
        ListNode n6 = new ListNode(5);
        ListNode n7 = new ListNode(6);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;

        ListNode nn = deleteDuplicates(n1);
        while (nn != null) {
            System.err.println(nn.val);
            nn = nn.next;
        }
    }

    /**
     * 哈希表
     * > 2022/08/24 15:15:28
     * 解答成功:
     * 	执行耗时:1 ms,击败了100.00% 的Java用户
     * 	内存消耗:40.7 MB,击败了95.21% 的Java用户
     * @param head
     * @return
     */
    public static ListNode deleteDuplicates(ListNode head) {
        //若头结点为空，返回null（不要返回new ListNode()，val会有默认值0）
        if (head == null) {
            return null;
        }
        //定义哈希表，并先存储头结点（可以使用int数组优化，但是可读性较差）
        HashSet<Integer> set = new HashSet<>();
        set.add(head.val);
        //定义当前结点前一结点
        ListNode preN = head;
        //定义当前结点
        ListNode stepN = preN.next;

        //若step未走尽，继续循环
        while (stepN != null) {
            //HashSet的add方法，当右相同元素时会false，所以加不成功就是有重复了，跳过即可
            if (!set.add(stepN.val)) {
                //当前结点的前一结点指向当前结点的后一结点
                preN.next = stepN.next;
            } else {
                //否则，更迭前一结点位置
                preN = stepN;
            }
            //无论如何，更迭当前结点位置：step结点右移
            stepN = stepN.next;
        }
        //返回百孔千疮的头结点[/狗头]
        return head;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
